package top.humbleyuan.sortmethod;

import java.util.Arrays;
import java.util.LinkedHashMap;
import java.util.Stack;

/**
 * @Author HumbleYuan
 * @Date 2020/3/2 21:47
 * @Des 堆排序是一种选择排序，由于堆顶元素不是最大就是最小，
 *      所以只要每次构造堆，取堆顶元素排序即可
 *      ***第一个非叶子节点：len / 2 -1
 *      ***当前节点的左节点：2*i + 1
 */
public class Heap {
    public static void main(String[] args) {
        int[] heap = {6,2,4,3,8,4,7};

        /*
            构造大顶堆
            从第一个非叶子节点开始构造
         */
        for (int i = heap.length / 2 - 1; i >= 0; i--) {
            buildHeap(i, heap,heap.length);
        }

        /**
         * 大顶堆顶是最大值，交换到最后，继续构造
         */
        for (int i = heap.length - 1; i > 0; i--) {
            swap(0,i,heap);
            buildHeap(0, heap, i);  // 这里只要调整顶上交换元素即可
        }

        System.out.println(Arrays.toString(heap));
    }

    public static void buildHeap(int i, int[] heap,int length) {
        // 这里因为子树有多层，要进行多层循环，所以先把父节点(顶)存下来，这样不用每次交换
        int temp = heap[i];

        // 开始调整当前非叶子节点及其子树的顺序,从该结点左子树开始
        for (int j = 2 * i + 1; j < length; j = j * 2 + 1) {
            // 目的是将最大的调整到这这棵子树的顶端
            // 先找到左右子树较大的
            if(j+1 < length && heap[j] < heap[j+1]) {
                j++;
            }

            // 若两子树中有大于父节点的树进行调整
            if(heap[j] > temp) {
                heap[i] = heap[j];
                i = j;  // 将当前子节点变成新的父节点
            } else {    // 若子树都比顶小直接跳出
                break;
            }
        }

        heap[i] = temp; // temp即最开始的顶放在最终位置
    }

    public  static void swap(int i,int j,int[] arr) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
